COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0BASL30\M1BASI30\M2SUB\M3NGR40\M4BDB30\.
C00006 00003	\\M0BASL30\M1BASI30\M2SUB\M3NGR40\M4BDB30\.
C00007 ENDMK
C⊗;
\\M0BASL30;\M1BASI30;\M2SUB;\M3NGR40;\M4BDB30;\.
\F3\CCOMPUTER SCIENCE DEPARTMENT
\CSTANFORD UNIVERSITY



\CCS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1973
\CFINAL EXAM
\F0\COpen Books and Notes



\J1.    \F1alt\F0[\F1u, m, n\F0] takes every \F1n\F0th element of the list \F1u\F0 starting
with the \F1m\F0th.  Write a recursive defintion of \F1alt\F0[\F1u, m, n\F0].



2.      \F1odds u\F0 is a list of the elements of the list \F1u\F0 that occur in \F1u\F0
an odd number of times.  Write the fastest definition of \F1odds u\F0 that you can.
Give several if you like, but be sure to have one that works.



3.      Let a graph \F1g\F0 be described as in chapter 1 of the notes and suppose that
whenever there is an edge from \F1x\F0 to \F1y\F0 there is also an edge from \F1y\F0
to \F1x\F0.  A component of the graph is a collection of vertices which are all connected to
each other by edge paths but not connected to any other vertices.  Write a function
to determine the number of components.



4.      The \F1n\F0th Fibonacci number is defined by the equations\.

	F\F20\F0 = 1
	F\F21\F0 = 1
	F\F2n+2\F0 = F\F2n+1\F0 + F\F2n\F0.

\JThus we have F\F22\F0 = 2, F\F23\F0 = 3, F\F24\F0 = 5, F\F25\F0 = 8, etc.

This definition translates into LISP as\.

	F\F2n\F0 ← \F4if\F1 n\F0 = 0 \F4∨ \F1n\F0 = 1 \F4then\F0 1 \F4else\F0 F\F2n-2\F0 + F\F2n-1\F0.

\J	What bad thing will happen if we try to compute F\F2100\F0 using this definition?
	Write a new LISP definition of F\F2n\F0 not suffering from this problem.



5.      Do \F4one\F0 of a and b.

	a.  Compare the  the compilation of ∧'s and ∨'s  in LCOM0 and
LCOM4.  Give  the simplest example you can of an expression for which
LCOM4 generates better code indicating the code generated by each.

	b.  The  definition of \F1ter\F0  in TICTAC2.LSP is  not very
elegant and  not very efficient.  Essentially  the same thing is done
better in the definition of \F1win\F0. Revise  \F1ter\F0 accordingly.
Likewise revise \F1imval\F0.\.
\\M0BASL30;\M1BASI30;\M2SUB;\M3NGR40;\M4BDB30;\.
\F3\CCOMPUTER SCIENCE DEPARTMENT
\CSTANFORD UNIVERSITY



\CCS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1973
\CFINAL EXAM

\CSolutions to Problems
\F0
	1. \F1alt[u,m,n] ← \F4if n \F1u \F4then \F0NIL \F4else if \F1m=1 \;
\F4then a \F1u . alt[\F4d \F1u,n,n] \F4else \F1alt[\F4d \F1u,m-1,n].